#include<iostream>
#include<algorithm>
#define N 10
using namespace std;
int w[] = { 0,3,1,2,2,1};
int v[] = { 0,10,3,9,5,6 };
/*
v：物品种类数量
w【】:重量数组
v【】：价值数组
c：背包总容量
*/
void  PackageHelper(int v,int w[], int p[] ,int c) {
	int dp[N][N] = { 0 };//初始化 
	
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= c; j++) {
			if (j >= w[i]) {
				//MAX二者选一个（不选，选） （前一个，前一个物品+当前价值物品） 
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]+p[i]]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	for (int i = 0; i <= v; i++) {
		for (int j = 0; j <= c; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}

	cout << endl << dp[v][c] << endl;
}

int main() {

	PackageHelper(6, w, v, 6);
	
	return 0;}
// 算法复杂度分析：
// (1）时间复杂度:算法中有主要的是两层嵌套的for循环，其时间复杂度为O(n*w)。
// (2）空间复杂度:由于二维数组c[n][w]，所以空间复杂度为O(n×w)。